package com.acwing.partition35;

import java.io.*;
import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2022/3/15 14:54
 */
public class AC3492负载均衡 {

    private static final int N = 200010;
    private static int[] w = new int[N];
    //堆中保存一个三元组 (恢复时间, 计算机编号, 恢复算力)
    private static PriorityQueue<int[]> heap = new PriorityQueue<>(N, (o1, o2) -> Integer.compare(o1[0], o2[0]));
    private static int n, m;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        ss = reader.readLine().split(" ");
        for (int i = 1; i <= n; i++) w[i] = Integer.parseInt(ss[i - 1]);
        for (int i = 0; i < m; i++) {
            ss = reader.readLine().split(" ");
            //读入任务时间、计算机编号、任务耗时、算力消耗
            int a = Integer.parseInt(ss[0]), b = Integer.parseInt(ss[1]), c = Integer.parseInt(ss[2]), d = Integer.parseInt(ss[3]);
            writer.write(resolve(a, b, c, d) + "\n");
        }
        writer.flush();
    }

    private static int resolve(int a, int b, int c, int d) {
        //先查询截止当前时间有没有可以恢复的算力
        while (!heap.isEmpty() && heap.peek()[0] <= a) {
            //取出信息，对计算机的算力进行补充
            int[] t = heap.poll();
            w[t[1]] += t[2];
        }
        //查看当前计算机是否能完成任务，如果不能完成，直接返回-1，如果能完成，扣除算力，并将恢复时间放入堆中
        if (w[b] < d) return -1;
        w[b] -= d;
        heap.add(new int[]{a + c, b, d});
        return w[b];
    }
}
